package com.zhugang.week11;

/**
 * @program algorithms
 * @description: cuttingRope
 * @author: chanzhugang
 * @create: 2022/09/02 12:22
 */
public class CuttingRope {

    /**
     * 剑指offer 14-I 剪绳子
     *
     * @param n
     * @return
     */
    public int cuttingRope(int n) {
        // n分成每段，求乘积最大：难理解
        // dp[i] : 长度为i的绳子切割之后的最大乘积
        // dp[i] = max(1 * dp[i - 1), 2 * dp[i - 2], 3 * dp[i - 3],.... i * dp[0])
        // 递归转非递归写法，类比上台阶
        if (n == 1) return 1;
        if (n == 2) return 1;
        if (n == 3) return 2;

        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                if (dp[i] < j * dp[i - j]) {
                    dp[i] = j * dp[i - j];
                }
            }
        }
        return dp[n];
    }

}